package com.millet.interview;

import java.util.Scanner;

/**
 * @author ZhangyiA
 * @describe:
 * @date 2021/07/03
 */

public class Two_WordSearch {

    //按照上下左右
    public int[] dx = {-1 , 1 , 0 , 0};
    public int[] dy = {0 , 0 , -1 , 1};

    public boolean dfs(char[][] board , char[] words , int x , int y , int index){
        //如果word的每个字符都查找完了，直接返回true
        if (index == words.length - 1)
            return true;

        //保留现场
        char temp = board[x][y];
        board[x][y] = '.';
        //上下左右遍历
        for(int i = 0 ; i < 4 ; i ++){
            int nx = dx[i] + x;
            int ny = dy[i] + y;
            //越界，或者当前单词不匹配
            if(nx < 0 || nx >= board.length || ny < 0 || ny >= board[0].length || board[nx][ny] != words[index + 1]) continue;
            if(dfs(board , words , nx , ny , index + 1)) return true;
        }
        board[x][y] = temp; //回溯，恢复现场
        return false;
    }

    public boolean exist(char[][] board , String word) {
        char[] words = word.toCharArray();
        for(int i = 0 ; i < board.length ; i ++){
            for(int j = 0 ; j < board[0].length ; j ++){
                //找到首字符后开始进行dfs搜索
                if(board[i][j] == words[0]){
                    if (dfs(board , words , i , j , 0))
                        return true;
                }
            }
        }
        return false;
    }

    public static void main(String[] args){
        Scanner input = new Scanner(System.in);
        String str = input.nextLine();
        // 数据处理
        String[] buff = str.split("]"); // 先通过 ] 进行划分得到行数
        int n = buff.length; // 有多少行
        int m = buff[0].substring(buff[0].lastIndexOf('[') + 1).split(",").length; // 因为这里第一行中是 [[A,B,C,E  , 因此需要根据出现最后一个 [ 划分得到  A,B,C,E
        char[][] board = new char[n][m];
        for(int i = 0 ; i < n ; i ++){
            String[] divide = buff[i].substring(buff[i].lastIndexOf('[') + 1).split(",");  // 再根据 , 划分就能得到每个 字母
            for(int j = 0 ; j < m ; j ++){
                board[i][j] = divide[j].charAt(0);
            }
        }
        String word = input.nextLine();
        Two_WordSearch wordSearch = new Two_WordSearch();
        System.out.println(wordSearch.exist(board , word));
    }
}
/*
[[A,B,C,E],[S,F,C,S],[A,D,E,E]]
SEE
* */